package 开始的剑指offer8月.查找算法;
// https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/submissions/
public class 剑指Offer53在排序数组中查找数字0816 {
    //暴力解也行
    class Solution {
        public int search(int[] nums, int target) {
            // 搜索右边界 right
            int i = 0, j = nums.length - 1;
            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] <= target) i = m + 1;
                else j = m - 1;
            }
            int right = i;
            // 若数组中无 target ，则提前返回
            if(j >= 0 && nums[j] != target) return 0;
            // 搜索左边界 right
            i = 0; j = nums.length - 1;
            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] < target) i = m + 1;
                else j = m - 1;
            }
            int left = j;
            return right - left - 1;
        }
    }
}
